As a tree-type index, a B-tree index has been widely used. Non-patent Document 1 below describes searching by using a B-tree, and an algorithm for inserting data into the B-tree and deleting data from the B-tree. Further, Non-patent Document 2 below describes the B-tree for a widely used relational database in ORACLE (registered trademark).
FIG. 10 illustrates a configuration example of the B-tree index based on FIG. 5 to FIG. 7 of Non-patent Document 2 below. In ORACLE (registered trademark), storage areas are managed using a certain unit (for example, 8 KB), and this unit is called a block. The block includes three types: a data block, a leaf block, and a branch block. The data block stores data rows as a whole. Indexes are stored in the leaf block and the branch block. Thus, the leaf block and the branch block are also called index blocks. The leaf block is a block at the lowest level of the index block. The branch block is a block having a link to the leaf block or another branch block.
At least one entry, which serves as the index, is stored in the leaf block and the branch block. In particular, the branch block in the highest level is also called a root block. Each entry contains a value of a column (hereinafter, referred to as a key) serving as a target of searching, and an identifier (ID). The identifier is data for identifying data row or other block. The identifier contained in the entry of the leaf block is used for identifying any one of data rows in the data block, and the identifier contained in the entry of the branch block is used for identifying any one of other branch blocks or any one of the leaf blocks. Thus, in order to identify a leaf block having a key satisfying a searching condition, a searcher sequentially compares keys in the branch block with data on the searching condition, and traces the branch block using the identifier.
The B-tree is designed by implicitly taking it into consideration that duplicating blocks from a slow hard disk to fast memory results in a bottleneck. Non-patent Document 1 below describes in the section “Balancing” that reading blocks involves disk access, and hence, it is important to maintain a low height for the B-tree. Actually, in a state where many blocks are stored on the hard disk and only a part of the blocks is cached in the memory, most of the blocks are read from the disk.
In this case, the disk accesses result in a bottleneck in the performance. This is because the latency of the access to the data on the memory and the data transfer rate (bandwidth) of the data on the memory are much better than those for the disk. Thus, the size of each of the blocks is set so as to be consistent with the unit of disk I/O to minimize the number of disk accesses.
Non-patent Documents 5 to 7 below each propose an idea of physical arrangement of data with the B-tree. Non-patent Document 5 below describes that, if a reference interval is less than or equal to five minutes, it is effective to place data in the memory rather than on the hard disk (5 minute rule), and if the number of instructions can be reduced by one every second by placing 10 bytes in the memory, this configuration is effective even if it uses more memory.
Below, the 5 minute rule will be described more in detail. The 5 minute rule is a turning point for deciding whether the placement of data in the memory is beneficial or not according to whether the following condition is satisfied or not, and if the reference interval R is five minutes, the following condition is satisfied.(A/R)−(M*B)=0
B<Bmax, A=2000, M=0.005, B=1333
Here, R is a reference interval, M is a unit price per byte of the memory, A is a unit price per bandwidth of the disk, B is a data size, and Bmax is a block size of the disk.
Non-patent Document 6 below describes that, in the environment 10 years after of Non-patent Document 1, it is effective to place blocks, randomly accessed at reference intervals of less than or equal to five minutes and blocks sequentially accessed at reference intervals of less than or equal to one minute, in the memory rather than on the hard disk. Further, in Non-patent Document 6 below, the appropriate block size for the B-tree is obtained on the basis of the time required for accessing the block modeled with the bandwidth and the latency of the disk, and the degree of narrowing the searching target by accessing the block.
Non-patent Document 7 below describes that, in the environment 20 years after of Non-patent Document 1 below, the 5 minute rule was established between the memory and the flash memory. Further, it also describes that the reference interval for storing data that have been stored in the disk into the flash memory is effectively two hours. In Non-patent Document 7 below, concerning the block size for the B-tree, it is effective to set the size of the disk to 512 KB and the size of the flash memory to 2 KB.
As a technique for improving the database performance as described above, an ORACLE (registered trademark) optimizer exists. Non-patent Document 8 below describes that, in a cost base optimizer (CBO), an operation cost COST used for preparing an appropriate implementation plan supporting a SQL statement is calculated through the following equation.
                    COST        =                                                                                                  IO_COST                    ×                    SREADTIM                                    +                                                                                                      CPU_COST                  /                                      (                                          CPUSPEED                      ×                      1000                                        )                                                                                SREADTIM                                    [                  Formula          ⁢                                          ⁢          1                ]            
The CPU_COST is a value that is in proportion to the number of cycles of a central processing unit (CPU) necessary for operation, and the IO_COST is a value that is in proportion to the number of blocks read through the operation. The SREADTIM is an average response time (msec) of random read from a disk with a single block, and the CPUSPEED is an average number of cycles (MHz) per second.
Non-patent Document 9 below describes that the number of blocks accessed in an insertion manipulation is calculated as a cost necessary for the insertion manipulation in the following manners (see pp. 20).Insertion cost=search cost+rewrite data block+rewrite index block+split rewrite=(3+1)+1+1+2=8blocks)
In Non-patent Document 9 below, a user needs to input an appropriate value for the number of the “split rewrite,” and by assuming that the height of the B-tree is 3, 3 is set in the “search cost.” Further, by assuming that the time required for access is constant, this time is calculated in the following manners (see pp. 371).Block access cost=disk access time to a block from a random starting location=average disk seek time+average rotational delay+block transfer
Patent Document 1 below proposes a database management system that selects an access path by considering the frequency of accesses to adjacent blocks. In the method described in Patent Document 1 below, an estimated time for execution is roughly calculated on the basis of the time for accessing adjacent blocks in the disk, the time required for accessing blocks that are not adjacent, the time required for processing each row, the number of blocks to be accessed, and the number of accesses to blocks that are not adjacent.